/*
Problem Description
要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。
 

Input
数据的第一行是一个T，表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
 

Output
对应每组数据输出(A/B)%9973。
 

Sample Input
2
1000 53
87 123456789
 

Sample Output
7922
6060
 */
package com.yuan.algorithms.training20150807;

import java.util.Scanner;

/**
 * @author YouYuan
 * @eMail E-mail:1265161633@qq.com
 * @Time 创建时间：2015年8月10日 下午8:34:54
 * @Explain 说明: A = n+9973k; (k为大于等于0的正整数) 
				    令C = A/B; 
				  C = t*9973 + x;这里x为所求（A/B)%9973; 
				    则A = B*C = B*t*9973 + B*x ; 
				  =>n+9973k = 9973Bt +Bx; 
				  =>9973k = 9973Bt + (Bx - n); 
				    所以(Bx - n)%9973 = 0; 
				    因为x<9973;枚举就可以解决 
 */
public class 数论_大数A除B模9973的结果 {

	static Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		while(in.hasNext()) {
			int t = in.nextInt();
			while(--t>=0) {
				long n = in.nextLong();
				int b = in.nextInt();
				long x = 0;
				while((b*x - n)%9973!=0) {
					x++;
				}
				System.out.println(x);
			}
		}
	}

}
